package com.base.dp;

/**
 * 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
 *
 * 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
 */
public class LongestPalindromeSubseq {
    public static void main(String[] args) {
        LongestPalindromeSubseq subseq = new LongestPalindromeSubseq();
        System.out.println(subseq.longestPalindromeSubseq("bbbab"));
    }
    public int longestPalindromeSubseq(String s){
        int length = s.length();
        if (length==0){
            return 0;
        }
        if (length  == 1 ){
            return 1;
        }
        // 定义dp[i][j]表示从下标i到下标j直接的最长子序列
        int[][] dp = new int[length][length];
        //dp[i][i] 都是等于1
        for (int i = 0; i < length; i++) {
            dp[i][i]= 1;
        }
        int max =0;
        //从长度等于2开始算计回文子序列,最长可能是字符串的长度        
        for (int len = 2; len <= length; len++) {
            //比如len = 6 ,从长度为2开始，那么i = [0,4]  j = [1,5]
            for (int i = 0; i <= length - len; i++) {
                int j =  i + len -1;  //当前i位置往后移动len的位置，然后下标从0开始，要-1
                if(s.charAt(i) == s.charAt(j)){
                    //如果相等，那么就在内部子串的基础上加2
                    dp[i][j] = dp[i+1][j-1] +2;  //i=0,j=1
                }else{
                    //不想等，那么就取最大值，dp[i+1][j] 和dp[i][j-1] 这里如何理解，
                    // 问dp[i+1][j]是啥意思，表示从下标i的后一个开始，到j的下标最长回文子序列,也就是没有加入s.charAt(i)
                    // 问dp[i][j-1]是啥意思，表示从下标i开始，到j-1的下标最长回文子序列，也就是没有加入s.charAt(j)
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]); //i=0,j=1
                    //问题是里面的值是否已经初始化完毕了
                    /**
                     * 1  0  0  0  0
                     * 0  1  0  0  0
                     * 0  0  1  0  0
                     * 0  0  0  1  0
                     * 0  0  0  0  1
                     */
                }
                if (dp[i][j]>max){
                    max = dp[i][j];
                }
            }
        }
        return max;
    }
}
